The objectives of this study are to ascertain the safety and tolerance of rPF4 when administered via 6 hour infusions at three different dose levels in a population of patients with cutaneous and/or visceral Kaposi's sarcoma, and to determine antitumor effects of rPF4 in this population.